package com.practice.niuke.new_direct_practice.class01;

import java.util.Arrays;

/**
 * 给定一个有序数组arr， 代表数轴上从左到右有n个点arr[0]、 arr[1]...arr[n-1]。 给定一
 * 个正数L， 代表一根长度为L的绳子， 求绳子最多能覆盖其中的几个点。
 */
public class Code01_CordCoverMaxPoint {

    /**
     * 使用“二分的方法”求解：
     * （1）以arr中的每个数arr[i]作为结束点，temp = arr[i]-L,
     * （2）在数组arr中以二分搜索的方法，找到“大于等于temp”最左侧的数的位置j在哪，
     * i-j+1就是以arr[i]结尾时最多能压着的数的个数。
     * （3）遍历一遍数组，每次使用（1）和（2）步求出一个最多能压着的数的个数，维护一个最大的数字即可！
     * 使用该方法时间复杂度的为O(n*logn)
     *
     * @param arr 数组
     * @param L   绳子的长度
     * @return int
     */
    public static int maxPoint1(int[] arr, int L) {
        int res = 1;
        // 遍历一遍数组
        for (int i = 0; i < arr.length; i++) {
            // 以arr中的每个数arr[i]作为结束点，temp = arr[i]-L,
            // 在数组arr中以二分搜索的方法，找到“大于等于temp”最左侧的数的位置j在哪。
            int nearest = nearestIndex(arr, i, arr[i] - L);
            res = Math.max(res, i - nearest + 1);
        }
        return res;
    }

    /**
     * 在数组arr中以“二分搜索的方法”，找到“大于等于value”最左侧的数的位置j在哪,
     *
     * @param arr   arr数组
     * @param R     最右侧位置
     * @param value value
     * @return “大于等于value”最左侧的数的位置j
     */
    public static int nearestIndex(int[] arr, int R, int value) {
        int L = 0;
        int index = R;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= value) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }

    /**
     * 使用“滑动窗口法”求解：
     * （1）定义一个变量left，定义一个变量right，left和right都是指向arr中元素的位置；
     * （2）保证left和right之间的距离（left和right之间数组元素的累加）不超过L；
     * （3）最开始left和right都指向数组arr[0]处，也就是left=right=0；
     * （4）当arr[right]-arr[left] <= L，且right<arr.length时，right向右移动，right++；
     * （5）当arr[right]-arr[left] > L时，right = right-1，此时right-left+1为“以arr[l]开头时能压中的最多数的个数”，
     * 此时若left<arr.length则left++，重复（4）（5）步，期间维护一个“以arr[l]开头时能压中的最多数的个数”的最大值。
     * 使用该方法时间复杂度的为O(n)
     *
     * @param arr 数组
     * @param L   绳子的长度
     * @return int
     */
    public static int maxPoint2(int[] arr, int L) {
        int left = 0;
        int right = 0;
        int N = arr.length;
        int max = 0;
        while (left < N) {
            while (right < N && arr[right] - arr[left] <= L) {
                right++;
            }
            max = Math.max(max, right - (left++));
        }
        return max;
    }

    // for test
    public static int test(int[] arr, int L) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            int pre = i - 1;
            while (pre >= 0 && arr[i] - arr[pre] <= L) {
                pre--;
            }
            max = Math.max(max, i - pre);
        }
        return max;
    }

    // for test
    public static int[] generateArray(int len, int max) {
        int[] ans = new int[(int) (Math.random() * len) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (int) (Math.random() * max);
        }
        Arrays.sort(ans);
        return ans;
    }

    public static void main(String[] args) {
        int len = 100;
        int max = 1000;
        int testTime = 100000;
        for (int i = 0; i < testTime; i++) {
            int L = (int) (Math.random() * max);
            int[] arr = generateArray(len, max);
            int ans1 = maxPoint1(arr, L);
            int ans2 = maxPoint2(arr, L);
            int ans3 = test(arr, L);
            if (ans1 != ans2 || ans2 != ans3) {
                System.out.println("oops!");
                break;
            }
        }

    }

}
